#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1 
#define ERROR 0
#define UNDERFLOW -1
#define OVERFLOW -2
#define MAXSIZE 12500
typedef int Status;
typedef int ElemType;
typedef struct
{
    int i, j; // 元素下标
    ElemType e;
}Triple;
typedef struct 
{
    Triple data[MAXSIZE + 1]; // data[0]不用
    int mu, nu, tu; // 行数、列数、元素个数
}TSMatrix;
// p99 algorithm 5.1
Status TranposeSMatrix(TSMatrix M, TSMatrix &T)
{
    T.mu = M.nu;
    T.nu = M.mu;
    T.tu = M.tu;
    if (T.tu)
    {
        int q = 1;
        for (int col = 1; col <= M.nu; ++col)
            for (int p = 1; p <= M.tu; ++p)
            {
                if (M.data[p].j == col)
                {
                    T.data[q].i = M.data[p].j;
                    T.data[q].j = M.data[p].i;
                    T.data[q].e = M.data[p].e;
                    ++q;
                }
            }
    }
    return OK;
}
// p100 algorithm 5.2
Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T)
{
    T.mu = M.nu;
    T.nu = M.mu;
    T.tu = M.tu;
    if (T.tu)
    {
        int * num = (int *)malloc((M.nu + 1) * sizeof(int));
        for (int col = 1; col < M.nu; ++col)
            num[col] = 0;
        for (int t = 1; t <= M.tu; ++t)
            ++num[M.data[t].j];
        int * cpot = (int *)malloc((M.nu + 1) * sizeof(int));
        cpot[1] = 1;
        for (int col = 2; col <= M.nu; ++col)
            cpot[col] = cpot[col - 1] + num[col - 1];
        free(num);
        num = NULL;
        for (int p = 1; p <= M.tu; ++p)
        {
            int col = M.data[p].j;
            int q = cpot[col];
            T.data[q].i = M.data[p].j;
            T.data[q].j = M.data[p].i;
            T.data[q].e = M.data[p].e;
            ++cpot[col];
        }
        free(cpot);
        cpot = NULL;  
    }
    return OK;
}

int main(void)
{
    return 0;
}
